// https://www.lintcode.com/problem/kth-smallest-numbers-in-unsorted-array/description

class Solution {
public:
    /**
     * @param k: An integer
     * @param nums: An integer array
     * @return: kth smallest element
     */
    // O(nlogn)
    // int kthSmallest(int k, vector<int> &nums) {
    //     sort(nums.begin(), nums.end());
    //     return nums[k - 1];
    // }
    
    // partion: 平均时间复杂度O(n)，最差时间复杂度O(n2)
    // 注意必须倒排，剩下一半是不排序的！！
    void partion(vector<int> &nums, int start, int end, int k)
    {
        int low = start;
        int high = end;
        int mid = (high - low) / 2 + low;
        int p = nums[mid]; // 注意记录下来，不然swap操作之后nums[mid]可能变化！！
        while (low < high)
        {
            // while (nums[low] < nums[p])
            while (nums[low] < p)
                low++;
            while (nums[high] > p)
                high--;
            if (low <= high)
            {
                swap(nums[low++], nums[high--]);
            }
        }
        // if (low < end && k > low) 
        if (low < end && k >= low) 
            partion(nums, low, end, k);
        // if (high > start && k < high)
        if (high > start && k <= high)
            partion(nums, start, high, k);
    }
    int kthSmallest(int k, vector<int> &nums) {
        partion(nums, 0, nums.size() - 1, k);
        return nums[k - 1];
    }
};